Generally, in a nonvolatile memory such as a flash memory, data cannot be overwritten on stored data, and is required to be written after the stored data is erased. The repeated write and erase operations leave unwanted divided areas where the data remain unerased. The process of erasing these unwanted areas and forming a continuous area having no data written therein is called compaction or garbage collection. The garbage collection process in a conventional semiconductor storage device is described in, for example, Jpn. Pat. Appln. KOKOAI Publication No. 6-222985 (Paragraphs 0011 to 0015, 0028, 0039 and 0050).
According to this conventional technique, data D is written at an address (A, a) of a memory based on a write request from a host. After that, in response to another write request from the host to the frame of address (A, a), a new version of data D-1 is written in the data field of, for example, an address (B, m) where no data is written as yet. In the pointer field of the address (A, a), “B, m” is written as the address of the link destination. After that, in response to another request from the host to write in the address (A, a), data D-2 is written in a frame having no data written therein such as the data field of an address (C, n). In the pointer field of the address (B, m), “C, n” is written as the address of the link destination.
In the case where the garbage collection is effected in this manner, the frame of the address (B, m) only indicates the link relation and has no meaning as data. Therefore, this frame of “B, m” is erased by the garbage collection process.
In this process, the first step is to save the frame data of the address (A, a) in a buffer, and the pointer thereof is rewritten to “C, n” on the buffer. At the same time, the data of the addresses (B, m) and (A, a) are erased. After that, the data of the address (A, a) for which the pointer is rewritten is written in the same address of the memory. As a result, the link destination of the address (A, a) directly changes to (C, n), and the frame of the address (B, m) becomes the one in which the data can be written.
In the case where the rewrite control operation is performed according to the pointer field as described above, however, the link destination is required to be tracked in response to a write request from the host, thereby posing a problem that a considerable time is required. In view of this, a table including a designated address field, a valid bit field and a logic address field is provided according to Jpn. Pat. Appln. KOKOAI Publication No. 6-222985. The designated address field indicates the address designated by the host at the time of accessing data in the nonvolatile memory from the host. The valid bit field indicates whether the data is stored in the corresponding block of the memory. In the logic address field, the address designated by the host is logically converted to determine the address of the block of the memory.
A garbage collection controller has a preset threshold value, and upon reception of a write request from the host, determines, with reference to the table described above, whether the sum of the number of blocks in which the data is written and the number of memory blocks for executing the write request exceeds a threshold value or not. In the case where the sum exceeds the threshold value, the garbage collection control unit carries out the garbage collection for the memory. The threshold value is set at an appropriate value such as a value representing 90% of the replacement area of the memory. Since the garbage collection is carried out based on the threshold value as described above, the requirement to execute the garbage collection process while the write request from the host is being processed can be avoided.
Further, according to Jpn. Pat. Appln. KOKOAI Publication No. 6-222985, the garbage collection control unit has a timer function. Thus, the garbage collection controller monitors the operation of the blocks of the memory with reference to the table, and in the case where the state of a particular memory block is not more than the threshold value, writes the data in the memory block while setting the timer. In the case where the state of the memory block is more than the threshold value, on the other hand, the garbage collection is carried out for the memory while resetting the timer. The garbage collection controller thus carries out the garbage collection upon lapse of a predetermined time with the timer set. Also by carrying out the garbage collection at regular time intervals in this way, the requirement to execute the garbage collection process while the write request from the host is being processed can be avoided.
The device described in Jpn. Pat. Appln. KOKOAI Publication No. 6-222985 carries out the garbage collection at regular time intervals. In order to carry out the garbage collection, the garbage collection controller is required to access the table and search for an address of a frame in which no data is written. This poses a problem that the search process represents a considerable part of the time of the garbage collection as a whole.